// 1.创建Node节点类
/**
 * Node节点类，表示链表中的一个节点。
 * @template T - 节点存储的值的类型
 */
class Node<T> {
  value: T;
  next: Node<T> | null = null;

  /**
   * @param {T} value - 节点存储的值
   */
  constructor(value: T) {
    this.value = value;
  }
}

// 2.创建LinkedList的类
/**
 * LinkedList 链表类，支持链表的基本操作。
 * @template T - 链表存储的值的类型
 */
class LinkedList<T> {
  head: Node<T> | null = null;
  private size: number = 0;

  /**
   * 获取链表的长度。
   * @return {number} 链表的节点数量
   */
  get length() {
    return this.size;
  }

  /**
   * 根据位置获取节点（不是节点的值）。
   * @param {number} position - 节点的位置（从0开始）
   * @return {Node<T> | null} 返回指定位置的节点，如果超出范围则返回 null
   */
  private getNode(position: number): Node<T> | null {
    let index = 0;
    let current = this.head;
    while (index++ < position && current) {
      current = current?.next;
    }
    return current;
  }

  /**
   * 向链表末尾追加一个新的节点。
   * @param {T} value - 要追加的值
   */
  append(value: T) {
    const newNode = new Node(value);

    if (!this.head) {
      this.head = newNode;
    } else {
      let current = this.head;
      while (current.next) {
        current = current.next;
      }
      current.next = newNode;
    }

    this.size++;
  }

  /**
   * 遍历链表并输出所有节点的值。
   */
  traverse() {
    const values: T[] = [];
    let current = this.head;
    while (current) {
      values.push(current.value);
      current = current.next;
    }
    console.log(values.join('->'));
  }

  /**
   * 在指定位置插入一个新的节点。
   * @param {T} value - 要插入的值
   * @param {number} position - 要插入的位置（从0开始）
   * @return {boolean} 如果插入成功返回 true，否则返回 false
   */
  insert(value: T, position: number): boolean {
    if (position < 0 || position > this.size) {
      console.error(`传入的${position}越界了`);
      return false;
    }

    const newNode = new Node(value);

    if (position === 0) {
      newNode.next = this.head;
      this.head = newNode;
    } else {
      const previous = this.getNode(position - 1);
      newNode.next = previous?.next ?? null;
      previous!.next = newNode;
    }

    this.size++;
    return true;
  }

  /**
   * 删除指定位置的节点。
   * @param {number} position - 要删除节点的位置（从0开始）
   * @return {T | null} 返回删除的节点的值，如果删除失败则返回 null
   */
  removeAt(position: number): T | null {
    if (position < 0 || position >= this.size) return null;

    let current = this.head;

    if (position === 0) {
      this.head = this.head!.next;
    } else {
      const previous = this.getNode(position - 1);
      previous!.next = previous?.next?.next ?? null;
    }

    this.size--;
    return current!.value;
  }

  /**
   * 删除指定值的节点。
   * @param {T} value - 要删除的值
   * @return {T | null} 返回删除的节点的值，如果没有找到则返回 null
   */
  remove(value: T): T | null {
    const index = this.indexOf(value);
    return this.removeAt(index);
  }

  /**
   * 获取指定位置的节点值。
   * @param {number} position - 节点的位置（从0开始）
   * @return {T | null} 返回指定位置的节点值，如果位置超出范围则返回 null
   */
  get(position: number): T | null {
    if (position < 0 || position > this.size) return null;
    return this.getNode(position)?.value ?? null;
  }

  /**
   * 更新指定位置的节点值。
   * @param {T} value - 新的值
   * @param {number} position - 要更新节点的位置（从0开始）
   * @return {boolean} 如果更新成功返回 true，否则返回 false
   */
  update(value: T, position: number): boolean {
    if (position < 0 || position >= this.size) return false;

    const currentNode = this.getNode(position);
    currentNode!.value = value;
    return true;
  }

  /**
   * 获取指定值的索引。
   * @param {T} value - 要查找的值
   * @return {number} 返回值的索引，如果不存在则返回 -1
   */
  indexOf(value: T): number {
    let current = this.head;
    let index = 0;
    while (current) {
      if (current.value === value) {
        return index;
      }
      current = current.next;
      index++;
    }
    return -1;
  }

  /**
   * 判断链表是否为空。
   * @return {boolean} 如果链表为空返回 true，否则返回 false
   */
  isEmpty() {
    return this.size === 0;
  }
}

// 测试
const linkedList = new LinkedList<string>();
linkedList.append('aaa');
linkedList.append('bbb');
linkedList.append('ccc');

linkedList.insert('abc', 0);
linkedList.traverse();
linkedList.insert('cba', 2);
linkedList.traverse();

console.log(linkedList.removeAt(0));
console.log(linkedList.removeAt(3));
linkedList.traverse();
console.log(linkedList.get(1));

console.log(linkedList.update('update', 1));
linkedList.traverse();
console.log(linkedList.indexOf('update'));
console.log(linkedList.indexOf('empty'));
console.log(linkedList.remove('update'));
console.log(linkedList.isEmpty());
linkedList.traverse();

export { Node };
